package sol.leetcode;

import java.util.Arrays;

/**
 * Sort Colors
 */
public class Issue075 {
    public void sortColors(int[] nums) {
        //for (int i = 1; i < nums.length; ++i) {
        //    for (int j = i; j > 0; --j) {
        //        if (nums[j] < nums[j - 1]) {
        //            int tmp = nums[j];
        //            nums[j] = nums[j - 1];
        //            nums[j - 1] = tmp;
        //        }
        //    }
        //}
        int p = 0;
        int q = nums.length - 1;
        int i = 0;
        while (i <= q) {
            if (nums[i] == 0) {
                swap(nums, i, p);
                ++i;
                ++p;
            } else if (nums[i] == 2) {
                swap(nums, i, q);
                q--;
            } else {
                i++;
            }
        }
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {1, 0, 1, 0, 1, 2, 1, 0, 2};
        new Issue075().sortColors(nums);
        System.out.println(Arrays.toString(nums));
    }
}
